// 95.不同的二叉搜索树2
package Leetcode_Second_Brush;

import java.util.ArrayList;
import java.util.List;

public class Solution095 {
    public List<TreeNode> generateTrees(int n) {
        return recursion(1, n);
    }

    // 根据 left~right 的值所能构造的所有二叉搜索树
    private List<TreeNode> recursion(int left, int right) {
        List<TreeNode> roots = new ArrayList<>();

        // 此时无法构造二叉搜索树，返回 null
        if (left > right) {
            roots.add(null);
            return roots;
        }

        // 枚举范围内的头节点
        for (int i = left; i <= right; i++) {
            // 自上而下进行递归获取不同的左右子树，左右子树都是二叉搜索树
            List<TreeNode> leftRoots = recursion(left, i - 1);
            List<TreeNode> rightRoots = recursion(i + 1, right);
            // 自下而上拼接左右子树
            for (TreeNode leftRoot : leftRoots) {
                for (TreeNode rightRoot : rightRoots) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftRoot;
                    root.right = rightRoot;
                    roots.add(root);
                }
            }
        }
        return roots;
    }
}
